package com.lk.common.utils.datastructure;

/**
 * 冒泡排序算法，三种实现
 * @author lijun 
 * @since 2018-05-15
 */
public class BubbleSort {
	
	public static void main(String[] args) {  
		int[] arr = {1,8,3,6,4,3,2};
		if(arr.length>0) {
			bubbleSort1(arr,arr.length);
		}
		for(int i=0;i<arr.length;i++) {
			System.out.println(arr[i]);
		}
    }  
	
	/**
	 * 冒泡排序的第一种实现, 没有任何优化
	 * @param a
	 * @param n
	 */
	public static void bubbleSort1(int [] a, int n){
	    int i, j;

	    for(i=0; i<n; i++){//表示n次排序过程。
	        for(j=1; j<n-i; j++){
	            if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
	                //交换a[j-1]和a[j]
	                int temp;
	                temp = a[j-1];
	                a[j-1] = a[j];
	                a[j]=temp;
	            }
	        }
	    }
	}
	
	/**
	 * 设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
	 * @param a
	 * @param n
	 */
	public static void bubbleSort2(int [] a, int n){
	    int j, k = n;
	    boolean flag = true;//发生了交换就为true, 没发生就为false，第一次判断时必须标志位true。
	    while (flag){
	        flag=false;//每次开始排序前，都设置flag为未排序过
	        for(j=1; j<k; j++){
	            if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
	                //交换a[j-1]和a[j]
	                int temp;
	                temp = a[j-1];
	                a[j-1] = a[j];
	                a[j]=temp;

	                //表示交换过数据;
	                flag = true;
	            }
	        }
	        k--;//减小一次排序的尾边界
	    }
	}
	
	/**
	 * 第三种冒泡排序算法
	 * @param a
	 * @param n
	 */
	public static void bubbleSort3(int [] a, int n){
	    int j , k;
	    int flag = n ;//flag来记录最后交换的位置，也就是排序的尾边界

	    while (flag > 0){//排序未结束标志
	        k = flag; //k 来记录遍历的尾边界
	        flag = 0;

	        for(j=1; j<k; j++){
	            if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
	                //交换a[j-1]和a[j]
	                int temp;
	                temp = a[j-1];
	                a[j-1] = a[j];
	                a[j]=temp;

	                //表示交换过数据;
	                flag = j;//记录最新的尾边界.
	            }
	        }
	    }
	}
}
